package sort;

import java.time.LocalDateTime;

import utils.FileUtils;
import utils.SortUtils;

//基数排序
public class RadixSort {
    public static void main(String[] args) {
        // 需要加载的排序的文件，n-普通版本，数据范围在int范围内，1k - 1000个数据的文件
//		String fileName = "n_1k";
//		String fileName = "n_1w";
		String fileName = "n_10w";
//        String fileName = "n_100w";
//		String fileName = "n_500w";

        // 数据文件加载
        long startTime = System.currentTimeMillis();
        String readText = FileUtils.readText(SortUtils.FILE_PREFIX + fileName);
        String[] numString = readText.split(" ");
        long endTime = System.currentTimeMillis();
        System.out.println(fileName + "数据文件加载共耗时：" + (endTime - startTime) + "ms");

        // 基数排序
        startTime = System.currentTimeMillis();
        int[] num = radixSort(numString);
        endTime = System.currentTimeMillis();
        System.out.println(fileName + "数据进行基数排序共耗时：" + (endTime - startTime) + "ms");

        // 正确性验证
        startTime = System.currentTimeMillis();
        SortUtils.validate(num);
        endTime = System.currentTimeMillis();
        System.out.println(fileName + "基数排序正确性验证共耗时：" + (endTime - startTime) + "ms");
    }

    // 基数排序
    public static int[] radixSort(String[] numString) {
        // 数据预处理
        Long[] arr = new Long[numString.length];
        // 找出最大位数(即代表循环轮数)
        Long max = 0L;
        for (int i = 0; i < numString.length; i++) {
            // 由于负数存在，所有数据加上Integer.MAX_VALUE，全部转为正数
            arr[i] = Long.valueOf(numString[i]) + Integer.MAX_VALUE;
            if (arr[i] > max)
                max = arr[i];
        }
        numString = null;

        // 开始基数排序
        return sort(arr, max);
    }

    public static int[] sort(Long[] arr, Long max) {
        Long[][] buckets = new Long[10][arr.length]; // 10个桶，每个桶又是一维数组
        int[] bucketNum = new int[10]; // 每个桶当前存储数的数量
        int circularNum = (max + "").length(); // 循环轮数
        for (int i = 0, n = 1; i < circularNum; i++, n *= 10) {
            for (Long value : arr) {
                int bit = (int) (value / n % 10); // 个位、十位、百位、... bit表示存到第几桶
                buckets[bit][bucketNum[bit]++] = value;
            }
            // 桶里的数按顺序存回arr
            int index = 0;
            for (int j = 0; j < buckets.length; j++) {
                for (int k = 0; k < bucketNum[j]; k++) {
                    arr[index++] = buckets[j][k];
                }
                bucketNum[j] = 0; // 清空该桶（实际上没有清空，不过后续都会被覆盖）
            }
        }
        // 恢复为原始数据大小，并返回数组
        return resetNum(arr);
    }

    // 基数排序加权值的long数组恢复成原值的int数组
    static int[] resetNum(Long[] arr) {
        int[] resultNum = new int[arr.length];
        for (int i = 0; i < resultNum.length; i++) {
            resultNum[i] = (int) (arr[i] - Integer.MAX_VALUE);
        }
        return resultNum;
    }
}
